﻿using System;
using System.Collections;
using System.Collections.Generic;
using JetBrains.Annotations;

namespace DiffLib
{
    /// <summary>
    /// This class implements the basic diff algorithm by recursively applying the Longest Common Substring
    /// on pieces of the collections, and reporting sections that are similar, and those that are not,
    /// in the appropriate sequence.
    /// </summary>
    /// <typeparam name="T">
    /// The types of elements in the collections being compared.
    /// </typeparam>
    [PublicAPI]
    public sealed class Diff<T> : IEnumerable<DiffChange>
    {
        private readonly int _Collection1Length;
        private readonly int _Collection2Length;
        private readonly LongestCommonSubstring<T> _LongestCommonSubstring;
        private readonly IEqualityComparer<T> _Comparer;
        private readonly IList<T> _RandomAccess1;
        private readonly IList<T> _RandomAccess2;

        /// <summary>
        /// Initializes a new instance of <see cref="Diff{T}"/>
        /// using the default <see cref="IEqualityComparer{T}"/> instance for the
        /// <typeparamref name="T"/> type.
        /// </summary>
        /// <param name="collection1">
        /// The first collection of items.
        /// </param>
        /// <param name="collection2">
        /// The second collection of items.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// <para><paramref name="collection1"/> is <c>null</c>.</para>
        /// <para>- or -</para>
        /// <para><paramref name="collection2"/> is <c>null</c>.</para>
        /// </exception>
        [PublicAPI]
        public Diff([NotNull] IEnumerable<T> collection1, [NotNull] IEnumerable<T> collection2)
            : this(collection1, collection2, EqualityComparer<T>.Default)
        {
            // Nothing here
        }

        /// <summary>
        /// Initializes a new instance of <see cref="Diff{T}"/>.
        /// </summary>
        /// <param name="collection1">
        /// The first collection of items.
        /// </param>
        /// <param name="collection2">
        /// The second collection of items.
        /// </param>
        /// <param name="comparer">
        /// The <see cref="IEqualityComparer{T}"/> that will be used to compare elements from
        /// <paramref name="collection1"/> with elements from <paramref name="collection2"/>.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// <para><paramref name="collection1"/> is <c>null</c>.</para>
        /// <para>- or -</para>
        /// <para><paramref name="collection2"/> is <c>null</c>.</para>
        /// <para>- or -</para>
        /// <para><paramref name="comparer"/> is <c>null</c>.</para>
        /// </exception>
        [PublicAPI]
        public Diff([NotNull] IEnumerable<T> collection1, [NotNull] IEnumerable<T> collection2, [NotNull] IEqualityComparer<T> comparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            _RandomAccess1 = collection1.ToRandomAccess();
            _RandomAccess2 = collection2.ToRandomAccess();

            _Collection1Length = _RandomAccess1.Count;
            _Collection2Length = _RandomAccess2.Count;
            _LongestCommonSubstring = new LongestCommonSubstring<T>(_RandomAccess1, _RandomAccess2, comparer);
            _Comparer = comparer;
        }

        #region IEnumerable<DiffChange> Members

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        /// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>1</filterpriority>
        [PublicAPI]
        [NotNull]
        public IEnumerator<DiffChange> GetEnumerator()
        {
            return Generate().GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        /// <summary>
        /// Generates the diff between the two collections.
        /// </summary>
        [NotNull]
        [PublicAPI]
        public IEnumerable<DiffChange> Generate()
        {
            return GenerateSections(0, _Collection1Length, 0, _Collection2Length);
        }

        [NotNull]
        private IEnumerable<DiffChange> GenerateSections(int lower1, int upper1, int lower2, int upper2)
        {
            // First do some basic elementary "diffs", basically when we're done with either one or both collections

            // No elements left in either source
            if (lower1 == upper1 && lower2 == upper2)
                return new DiffChange[0];

            // We got elements left in the second source (but the first is empty)
            if (lower1 == upper1)
                return new[] { new DiffChange(false, 0, upper2 - lower2) };

            // We got elements left in the first source (but the second is empty)
            if (lower2 == upper2)
                return new[] { new DiffChange(false, upper1 - lower1, 0) };

            // Now start the general processing
            return GenerateSectionsHandleEqualStartFirst(lower1, upper1, lower2, upper2);
        }

        [NotNull]
        private IEnumerable<DiffChange> GenerateSectionsHandleEqualStartFirst(int lower1, int upper1, int lower2, int upper2)
        {
            // We got elements left in both sources, so first figure out how much, if anything, is equal at the start of both
            int equalElementsAtTheStart = 0;
            while (lower1 + equalElementsAtTheStart < upper1 && lower2 + equalElementsAtTheStart < upper2 && _Comparer.Equals(_RandomAccess1[lower1 + equalElementsAtTheStart], _RandomAccess2[lower2 + equalElementsAtTheStart]))
                equalElementsAtTheStart++;

            if (equalElementsAtTheStart > 0)
            {
                // First yield the equal block at the start
                yield return new DiffChange(true, equalElementsAtTheStart, equalElementsAtTheStart);

                // Recursively process rest of collections
                foreach (var section in GenerateSections(lower1 + equalElementsAtTheStart, upper1, lower2 + equalElementsAtTheStart, upper2))
                    yield return section;
            }
            else
                foreach (var diffChange in GenerateSectionsHandleEqualEndNext(lower1, upper1, lower2, upper2))
                    yield return diffChange;
        }

        [NotNull]
        private IEnumerable<DiffChange> GenerateSectionsHandleEqualEndNext(int lower1, int upper1, int lower2, int upper2)
        {
            // Then figure out how much, if anything, is equal at the end of both
            int equalElementsAtTheEnd = 0;
            while (upper1 - equalElementsAtTheEnd > lower1 && upper2 - equalElementsAtTheEnd > lower2 && _Comparer.Equals(_RandomAccess1[upper1 - equalElementsAtTheEnd - 1], _RandomAccess2[upper2 - equalElementsAtTheEnd - 1]))
                equalElementsAtTheEnd++;
            if (equalElementsAtTheEnd > 0)
            {
                // Recursively process rest of collections
                foreach (var section in GenerateSections(lower1, upper1 - equalElementsAtTheEnd, lower2, upper2 - equalElementsAtTheEnd))
                    yield return section;

                // Then yield the equal block at the end
                yield return new DiffChange(true, equalElementsAtTheEnd, equalElementsAtTheEnd);
            }
            else
                // Recursively process section in the middle, using Longest Common Substring
                foreach (var section in GenerateSectionsUsingLongestCommonSubstring(lower1, upper1, lower2, upper2))
                    yield return section;
        }

        [NotNull]
        private IEnumerable<DiffChange> GenerateSectionsUsingLongestCommonSubstring(int lower1, int upper1, int lower2, int upper2)
        {
            LongestCommonSubstringResult lcsr = _LongestCommonSubstring.Find(lower1, upper1, lower2, upper2);

            // No common section was found, which means we can just flag the two portions of the collections as unequal and move on.
            if (lcsr == null)
                yield return new DiffChange(false, upper1 - lower1, upper2 - lower2);
            else
            {
                // Recursively process collections before the Longest Common Substring
                if (lower1 < lcsr.PositionInCollection1 || lower2 < lcsr.PositionInCollection2)
                    foreach (DiffChange prevSection in GenerateSections(lower1, lcsr.PositionInCollection1, lower2, lcsr.PositionInCollection2))
                        yield return prevSection;

                // Yield the Longest Common Substring
                yield return new DiffChange(true, lcsr.Length, lcsr.Length);

                // Recursively process collections after the Longest Common Substring
                if (lcsr.PositionInCollection1 + lcsr.Length < upper1 || lcsr.PositionInCollection2 + lcsr.Length < upper2)
                    foreach (DiffChange nextSection in GenerateSections(lcsr.PositionInCollection1 + lcsr.Length, upper1, lcsr.PositionInCollection2 + lcsr.Length, upper2))
                        yield return nextSection;
            }
        }
    }
}